from pynumpak.type import Interval, func_t


def fzero(func: func_t, ab: Interval, max_iter: int = 100, x_tol: float = 2 ** (-51),
          f_tol: float = 1e-10, show_iter_time: bool = False):
    """zeroin 算法. 要求 func(a) 与 func(b) 异号"""
    # 实现来自喻文健《数值分析与算法设计》
    a, b = ab
    assert func(a) * func(b) <= 0
    c = a
    d = b - c
    e = d

    for i in range(max_iter + 1):
        if func(a) == 0:
            return a if not show_iter_time else (a, i)
        if func(b) == 0:
            return b if not show_iter_time else (b, i)

        if func(a) * func(b) > 0:
            a = c
            d = b - c
            e = d

        if abs(func(a)) < abs(func(b)):
            c = b
            a, b = b, a

        m = (a - b) / 2
        tol = 2 * max(abs(b), 1) * x_tol
        if abs(a - b) < 2 * tol or abs(func(b)) < f_tol:
            return b if not show_iter_time else (b, i)

        if abs(e) < tol or abs(func(c)) <= abs(func(b)):
            d = m
            e = m
        else:
            s = func(b) / func(c)
            if a == c:
                p = 2 * m * s
                q = 1 - s
            else:
                q = func(c) / func(a)
                r = func(b) / func(a)
                p = s * (2 * m * q * (q - r) - (b - c) * (r - 1.0))
                q = (q - 1) * (r - 1) * (s - 1)

            if p > 0:
                q = -q
            else:
                p = -p

            if 2 * p < 3 * m * q - abs(tol * q) and p < abs(e * q / 2):
                e = d
                d = p / q
            else:
                d = m
                e = m

        c = b
        if abs(d) > tol:
            b += d
        else:
            b += tol if a > b else -tol

    raise ValueError("Unable to coverage")
